# 给你一个字符串 s，找到 s 中最长的回文子串。 
# 
#  
# 
#  示例 1： 
# 
#  
# 输入：s = "babad"
# 输出："bab"
# 解释："aba" 同样是符合题意的答案。
#  
# 
#  示例 2： 
# 
#  
# 输入：s = "cbbd"
# 输出："bb"
#  
# 
#  示例 3： 
# 
#  
# 输入：s = "a"
# 输出："a"
#  
# 
#  示例 4： 
# 
#  
# 输入：s = "ac"
# 输出："a"
#  
# 
#  
# 
#  提示： 
# 
#  
#  1 <= s.length <= 1000 
#  s 仅由数字和英文字母（大写和/或小写）组成 
#  
#  Related Topics 字符串 动态规划 
#  👍 4092 👎 0


from typing import List


# leetcode submit region begin(Prohibit modification and deletion)
class Solution:
    def longestPalindrome(self, s: str) -> str:
        start, end = 0, 0
        for i in range(len(s)):
            left1, right1 = self.expand(s, i, i)
            left2, right2 = self.expand(s, i, i+1)
            if right1 - left1 > end - start:
                start, end = left1, right1
            if right2 - left2 > end - start:
                start, end = left2, right2
        return s[start: end + 1]

    # 扩展
    def expand(self, s, left, right):
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return left + 1, right - 1


# leetcode submit region end(Prohibit modification and deletion)


def log(*args, **kwargs):
    print(*args, **kwargs)


# n 位一维数组 [False] * n
# x列, y行 的二维数组 [[False] * x for _ in range(y)]
# [] 切片: 前闭后开


# 动态规划
# 回文串 + 左右相等 => 新回文
# 一个字符回文, 两个字符相等回文

# def longestPalindrome(self, s: str) -> str:
#     n = len(s)
#     if n < 2:
#         return s
#     max_len = 1
#     begin = 0
#     # dp[i][j] 表示 s[i...j] 是回文字符串
#     # 先初始化未实名
#     dp = [[False] * n for _ in range(n)]
#     # 长度为1的子串都回文
#     for i in range(n):
#         dp[i][i] = True
#
#     # 枚举子串长度, 2 - n
#     for l in range(2, n + 1):
#         for i in range(n):
#             # 右边界
#             j = i - 1 + l
#             if j >= n:
#                 break
#             if s[i] != s[j]:
#                 dp[i][j] = False
#             else:
#                 if j - i < 3:
#                     dp[i][j] = True
#                 else:
#                     dp[i][j] = dp[i + 1][j - 1]
#             if dp[i][j] and j - i + 1 > max_len:
#                 max_len = j - i + 1
#                 begin = i
#     return s[begin: begin + max_len]

# 中心扩展
# 以步长1, 2, 为中心扩展, 扩展到不能扩展为止
# 遍历数组, 记录最长
#     def expand(self, s, left, right):
#         while left >= 0 and right < len(s) and s[left] == s[right]:
#             left -= 1
#             right += 1
#         return left + 1, right - 1
#
#     def longestPalindrome(self, s: str) -> str:
#         start, end = 0, 0
#         for i in range(len(s)):
#             left1, right1 = self.expand(s, i, i)
#             left2, right2 = self.expand(s, i, i+1)
#             if right1 - left1 > end - start:
#                 start, end = left1, right1
#             if right2 - left2 > end - start:
#                 start, end = left2, right2
#         return s[start: end + 1]


if __name__ == '__main__':
    s = Solution()
    st1 = 'babad'
    r1 = s.longestPalindrome(st1)
    assert r1 == 'bab', r1
    st2 = 'cbbd'
    r2 = s.longestPalindrome(st2)
    assert r2 == 'bb', r2
